Fork me on GitHub

JavaScript — 基本算法学习

发表于 | 分类于
| 字数统计 3,515 | 阅读时长 15

JavaScript — 基本算法学习

学JS也挺久了也很少接触算法，最近看到《学习JavaScript数据结构与算法》出了第二版，还是很新的一门教材。就买来拜读了一下，然后整理下学习到的知识，方便日后温习。

PS:下面所有算法，我们都最多用push方法向数据结构添加元素，这样刻意简单，这是为了能够专注排序和搜索算法，语法为ES6。

1、冒泡排序 — O(n²)

说明：冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素向上移动至正确的顺序，就好像气泡升至表面一样。

tips：冒泡排序是性能最差的一个算法。

1
2
3
4
5
6
7
8
9
10
11
12
let bubbleSort = (arr) >= {
    for (let i = 0, len = arr.length; i < len; i++) {
        for (let j = 0; j < len - 1; j++) {
			if(arr[j] > arr[j + 1]) {
				[ arr[i], arr[j + 1] ] = [ arr[j + 1], arr[i] ];
			}
        }
	}
};
let arr = [5,4,3,2,1];
bubbleSort(arr);
console.log(arr); // [1,2,3,4,5]

注意当函数执行到 i=1 的时候，数字4和5已经是正确的排序了。尽管如此，后续比较中，它们还一直在进行着比较，即使这是不必要的。
如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较了。改进后的函数：

1
2
3
4
5
6
7
8
9
10
11
12
let modBubbleSort = (arr) >= {
    for (let i = 0, len = arr.length; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
			if(arr[j] > arr[j + 1]) {
				[ arr[i], arr[j + 1] ] = [ arr[j + 1], arr[i] ];
			}
        }
	}
};
let arr = [5,4,3,2,1];
modBubbleSort(arr);
console.log(arr); // [1,2,3,4,5]

2、选择排序 — O(n²)

说明：选择排序大概思路是找到数据结构中最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let selectionSort = (arr) >= {
	let len = arr.length,
		indexMin;
	for(let i = 0; i < len -1; i++) {
		indexMin = i;
		for(let j = i; j < len; j++) { // 找到最小值的索引
			if(arr[indexMin] > arr[j]) {
				indexMin = j;
			}
		}
		[ arr[i], arr[indexMin] ] = [ arr[indexMin], arr[i] ];
	}
}
let arr = [5,4,3,2,1];
selectionSort(arr);
console.log(arr); // [1,2,3,4,5]

3、插入排序

从第二项开始和第一项比较，如果第一项大于第二项则换位。

然后比较第三项和前面两项，如果第二比第三大则换位，再比较第一和第二，如果第一比第二大则换位，否则不动。

tip:排序小型数组时，此算法比选择排序和冒泡性能要好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let insertionSort = (arr) >= {
	let len = arr.length,
		j, temp;
	for(let i = 1; i < len; i++) { // 从arr[i]开始循环
		j = i; // 比较j次
		temp = arr[i];
		while(j > 0 && arr[j - 1] > temp) {
			arr[j] = arr[j-1];
			j--;
		}
		arr[j] = temp;
	}
}
let arr = [5,4,3,2,1];
insertionSort(arr);
console.log(arr); // [1,2,3,4,5]

4、归并排序 — O(nlog^n)

JavaScript的Arry类定义了一个sort函数用以排序数组。ECMAScript没有定义哪个排序算法，所以浏览器厂商可以自行去实现算法。

Fierfox使用归并排序作为sort的实现，Chrome使用了快速排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
let mergeSort = (arr) >= {
	arr = mergeSortRec(arr);
}
let mergeSortRec = (arr) >= {
	let len = arr.length;
	if(len === 1) {
		return arr;
	}
	let mid = (len / 2) | 0;
	left = arr.slice(0, mid);
	right = arr.slice(mid, len);
	return merge(mergeSortRec(left), mergeSortRec(right));
}
let merge = (left, right) >= {
	let result = [],
	il = 0,
	ir = 0;
	while(il < left.length && ir < right.length) {
		if(left[il] < right[ir]) {
			result.push(left[il++]);
		} else {
			result.push(right[ir++]);
		}
	}
	while(il < left.length) {
		result.push(left[il++]);
	}
	while(ir < right.length) {
		result.push(right[ir++]);
	}
	return result;
}
let arr = [5,4,3,2,1];
mergeSort(arr);
console.log(arr); // [1,2,3,4,5]

5、快速排序 — O(nlog^n)

快速排序复杂度比一般的 O(nlog^n) 要好。

和归并排序一样，快速排序也使用分治方法，将原始数组分为较小的数组。（但没有像归并那样将它们分隔开）

分为三个步骤：

（1）、从数组中选择中间一项作为主元（不推荐从数组第一项作为主元，最好是随机选择一个数组项或是中间项）。

（2）、创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指针直到我们找到比主元大的元素，
接着，移动右指针直到找到一个比主元小的元素，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这步叫划分操作。

（3）、接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前两个步骤，直至数组完全排序

参考：快速排序（Quicksort）的Javascript实现 - 阮一峰 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    var mid = ~~(arr.length / 2),
        midItem = arr.splice(mid, 1)[0],
        left = [],
        right = [];
    arr.forEach(function(item) {
        if (item <= midItem) left.push(item);
        else right.push(item);
    });
    var _left = quickSort(left),
        _right = quickSort(right);
    return _left.concat(midItem, _right);
}
let arr = [5, 4, 3, 2, 1];
console.log(quickSort(arr)); // [1,2,3,4,5]

参考：【前端也要学点算法】快速排序的JavaScript实现 - 韩子迟 - 博客园

如果需要排序的数组有大量重复元素，可以用基于三向切分的快速排序大幅度提高效率。
基础的快排，每一次递归，我们将数组拆分为两个，递归出口是数组长度为 <=1。思考这样一个场景，递归过程中某个数组为 [1, 1, 1, 1, 1, 1, 1, 1]，如果是原始的快排，还需要继续递归下去，实际上已经不需要。所以我们可以用三向切分，简单地说就是将数组切分为三部分，大于基准元素，等于基准元素，小于基准元素。

我们可以设置一个 mid 数组用来保存等于基准元素的元素集合，以前取的基准元素是数组中间位置的元素，其实任意一个即可，这里选了最后一个，比较方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function quickSort3Way(a) {
    if (a.length <= 1) return a;
  
    var last = a.pop()
      , left = []
      , right = []
      , mid = [last];
  
    a.forEach(function(item) {
      if (item < last)
        left.push(item);
      else if (item > last)
        right.push(item);
      else
        mid.push(item);
    });
  
    var _left = quickSort3Way(left)
      , _right = quickSort3Way(right);
  
    return _left.concat(mid, _right);
}
let arr = [5, 4, 3, 2, 1];
console.log(quickSort3Way(arr)); // [1,2,3,4,5]

一行代码写快排

1
2
3
function quickSort(a) {
    return a.length <= 1 ? a : quickSort(a.slice(1).filter(item => item <= a[0])).concat(a[0], quickSort(a.slice(1).filter(item => item > a[0])));
}

6、堆排序

堆排序是一种把数组当做二叉树来排序的算法。

分为四个步骤：

（1）、索引0是树的根节点。

（2）、除根节点外，任意节点N的父节点是N/2

（3）、节点L的左子节点是2*L

（4）、节点L的右子节点是2*R+1

1
2
3
4
5
6
7
8
9
let heapSort = (arr) => {
	let heapSize = arr.length;
	build(arr);
	while(heapSize > 1) {
		heapSize--;
		[ arr[0], arr[heapSize] ] = [ arr[heapSize], arr[0] ];
		heapify(arr, heapSize, 0);
	}
}

第一步，构造一个满足arr[parent(i)] >= arr[i]的堆结构。

第二步，交换堆里的第一个元素和最后一个元素的位置交换，这样，最大的值就会出现在它已排序的位置。

第二步可能会丢掉堆的属性。因此我们还需要执行一个heapify函数，再次将数组转换成堆，也就是说，它会找到当前堆的根节点，重新放到树的底部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
let build = (arr) => {
	let heapSize = arr.length;
	for(let i = (arr.length / 2) | 0; i >= 0; i--) {
		heapify(arr, heapSize, i);
	}
}
let heapify = (arr, heapSize, i) => {
	let left = i * 2 + 1,
		right = i * 2 + 2,
		largest = i;
	if(left < heapSize && arr[left] > arr[largest]) {
		largest = left;
	}
	if(right < heapSize && arr[right] > arr[largest]) {
		largest = right;
	}
	if(largest !== i) {
		[ arr[i], arr[largest] ] = [ arr[largest], arr[i] ];
		heapify(arr, heapSize, largest)
	}
}
let arr = [5,4,3,2,1];
heapSort(arr);
console.log(arr); // [1,2,3,4,5]

7、计数排序 — Ο(n+k)

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组Count_arr，其中第i个元素是待排序数组arr中值等于i的元素的个数。然后根据数组Count_arr来将arr中的元素排到正确的位置。

分为四个步骤：

（1）、找出待排序的数组中最大和最小的元素。

（2）、统计数组中每个值为i的元素出现的次数，存入数组Count_arr的第i项。

（3）、对所有的计数累加（从Count_arr中的第一个元素开始，每一项和前一项相加）。

（4）、反向遍历原数组：将每个元素i放在新数组的第Count_arr(i)项，每放一个元素就将Count_arr(i)减去1。

tip：计数排序是一个非基于比较的排序算法，快于任何比较排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function countSort(arr, min, max) {
    let i, z = 0, count = [];
    for (i = min; i <= max; i++) {
        count[i] = 0;
    }
    for (i=0; i < arr.length; i++) {
        count[arr[i]]++;
    }
    for (i = min; i <= max; i++) {
        while (count[i]-- > 0) {
            arr[z++] = i;
        }
    }
    return arr;
}
let arr = [5,4,3,2,1];
countSort(arr, 0, 5);
console.log(arr); // [1,2,3,4,5]

8、桶排序

桶排序是一种基于计数的排序算法，工作原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

当要被排序的数据内的数值是均匀分配的时候（每个桶下的数量相等），桶排序时间复杂度为 O(n)。

分为四个步骤：

（1）设置固定数量的空桶。

（2）把数据放到对应的桶中。

（3）对每个不为空的桶中数据进行排序。

（4）拼接从不为空的桶中数据，得到结果。

参考: JavaScript十大经典排序算法 - CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
let bucketSort = (arr, num) => { // arr为数组，num为桶的数量
    if (arr.length <= 1) {
        returnarray;
    }
    let len = arr.length,
        buckets = [],
        result = [],
        min = (max = arr[0]),
        regex = "/^[1-9]+[0-9]*$/",
        space,
        n = 0;
    num = num || (num > 1 && regex.test(num) ? num : 10);
    console.time("桶排序耗时:");
    for (let i = 1; i < len; i++) {
        min = min <= arr[i] ? min : arr[i];
        max = max >= arr[i] ? max : arr[i];
    }
    space = (max - min + 1) / num;
    for (let j = 0; j < len; j++) {
        let index = Math.floor((arr[j] - min) / space);
        if (buckets[index]) {
            //  非空桶，插入排序
            let k = buckets[index].length - 1;
            while (k >= 0 && buckets[index][k] > arr[j]) {
                buckets[index][k + 1] = buckets[index][k];
                k--;
            }
            buckets[index][k + 1] = arr[j];
        } else {
            //空桶，初始化
            buckets[index] = [];
            buckets[index].push(arr[j]);
        }
    }
    while (n < num) {
        result = result.concat(buckets[n]);
        n++;
    }
    console.timeEnd("桶排序耗时:"); // 0.06ms
    return result;
};
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bucketSort(arr, 4)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
let arr1 = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time("快速排序耗时:");
quickSort(arr1); // 用上面所实现的快速排序方法
console.timeEnd("快速排序耗时:");

可以看出桶排序比快速排序快了不少。

参考：深入解析桶排序及Node.js上JavaScript代码的实现

算法分析：

（1）如果使用基于比较的排序，快速排序，平均时间复杂度为O(nlogn) = O(9000000*log9000000)=144114616=1.44亿次比较。

（2）如果使用基于计数的排序，桶排序，平均的时候复杂度，可以控制在线性复杂度，当创建700桶时从200分到900分各一个桶，O(N)=O(9000000)，就相当于扫描一次900W条数据。

然后我对桶排序代价分析直接做一下通俗的总结吧。如果我们把一个数组分成N桶，N桶里面有M个元素，那么M个元素还是要用到比较排序，为了提高速度我们应该尽量避免使用“比较”排序，极限情况下每个桶只能得到一个数据，也就是函数中第二个参数为1，这时桶排序效率能够达到O(n)。

当然，做到这一点很不容易，数据量巨大的情况下，函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

9、基数排序（分布式排序）— O(d*(n+r))

参考：排序算法系列 - 基数排序

该参考下的基数排序过程图很形象的说明了排序的原理。

tip：该函数只适合用于都为整数的无序数组，还要求得最大位数（最大的整数的位数maxValue.toString().length）。

如果要考虑浮点数，我认为先把元素都映射为整数，再用排序，再映射回来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
let counter = [];
let radixSort = (arr, maxDigit) => { // maxDigit为最大位数
    let mod = 10;
    let dev = 1;
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        let pos = 0;
        for(let j = 0; j < counter.length; j++) {
            let value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}
let arr2 = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
quickSort(arr2, 2); // [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

10、希尔排序

希尔排序关键在于增量的设置,根据增量分割数组并逐步进行直接插入排序,增量逐趟减少,并最后使得整个数组基本有序,再对整体进行直接插入排序.

基本的思路就是根据增量分割数组,如var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

我们增量为5,则分割为

[3,15,46]

[44,36,4]

[38,26,19]

[5,27,50]

[47,2,48]

并对每一组进行直接插入排序
再把增量变为2(减半),再进行分割,直到增量为1,再对全体进行一次直接插入排序就可以了.

参考：基本算法学习(一)之希尔排序(JS) - 渣途 - SegmentFault

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let shellSort = arr => {
    var len = arr.length;
    gap = Math.floor(len / 2);
    while (gap !== 0) {
        for (var i = gap; i < len; i++) {
            var temp = arr[i];
            var j;
            for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
};
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(shellSort(arr)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

结束，以上为JavaScript实现十大经典排序方法。

-------------本文结束感谢您的阅读-------------
分享